/*************************************************************************
	> File Name: 019.removeNthFromEnd.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四  9/ 2 12:33:07 2021
 ************************************************************************/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
    p->next = head;
    struct ListNode *slow = p, *fast = head;
    //快指针先移动n步，然后再移动慢指针
    //当快指针到达NULL指针时，慢指针刚好到达要删除的节点的前一个位置
    while (n--) fast = fast->next;
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    struct ListNode *temp = slow->next;
    slow->next = temp->next;
    free(temp);
    return p->next;
}


